{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Columns to Make Sorted III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDeletionSize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删列造序 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定由<meta charset=\"UTF-8\" />&nbsp;<code>n</code>&nbsp;个小写字母字符串组成的数组<meta charset=\"UTF-8\" />&nbsp;<code>strs</code>&nbsp;，其中每个字符串长度相等。</p>\n",
    "\n",
    "<p>选取一个删除索引序列，对于<meta charset=\"UTF-8\" />&nbsp;<code>strs</code>&nbsp;中的每个字符串，删除对应每个索引处的字符。</p>\n",
    "\n",
    "<p>比如，有<meta charset=\"UTF-8\" />&nbsp;<code>strs = [\"abcdef\",\"uvwxyz\"]</code>&nbsp;，删除索引序列<meta charset=\"UTF-8\" />&nbsp;<code>{0, 2, 3}</code>&nbsp;，删除后为<meta charset=\"UTF-8\" />&nbsp;<code>[\"bef\", \"vyz\"]</code>&nbsp;。</p>\n",
    "\n",
    "<p>假设，我们选择了一组删除索引<meta charset=\"UTF-8\" />&nbsp;<code>answer</code>&nbsp;，那么在执行删除操作之后，最终得到的数组的行中的 <strong>每个元素</strong> 都是按<strong>字典序</strong>排列的（即&nbsp;<code>(strs[0][0] &lt;= strs[0][1] &lt;= ... &lt;= strs[0][strs[0].length - 1])</code>&nbsp;和&nbsp;<code>(strs[1][0] &lt;= strs[1][1] &lt;= ... &lt;= strs[1][strs[1].length - 1])</code> ，依此类推）。</p>\n",
    "\n",
    "<p>请返回<meta charset=\"UTF-8\" /><em>&nbsp;<code>answer.length</code>&nbsp;的最小可能值</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"babca\",\"bbazb\"]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：\n",
    "</strong>删除 0、1 和 4 这三列后，最终得到的数组是 strs = [\"bc\", \"az\"]。\n",
    "这两行是分别按字典序排列的（即，strs[0][0] &lt;= strs[0][1] 且 strs[1][0] &lt;= strs[1][1]）。\n",
    "注意，strs[0] &gt; strs[1] —— 数组 strs 不一定是按字典序排列的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"edcba\"]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>如果删除的列少于 4 列，则剩下的行都不会按字典序排列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"ghi\",\"def\",\"abc\"]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>所有行都已按字典序排列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == strs.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= strs[i].length &lt;= 100</code></li>\n",
    "\t<li><code>strs[i]</code>&nbsp;由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-columns-to-make-sorted-iii](https://leetcode.cn/problems/delete-columns-to-make-sorted-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-columns-to-make-sorted-iii](https://leetcode.cn/problems/delete-columns-to-make-sorted-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"babca\",\"bbazb\"]', '[\"edcba\"]', '[\"ghi\",\"def\",\"abc\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]) -> int:\n",
    "        count = 0\n",
    "        # 记录的是满足条件的所有列的每一个元素的的严格大于情况.\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "        for col in zip(*A):\n",
    "            # sign_1表示cuts是否全都为True\n",
    "            # sign_2表示当前列是否满足条件\n",
    "            sign_1 = sign_2 = True\n",
    "            for i in range(len(col)-1):\n",
    "                if not cuts[i]:\n",
    "                    sign_1 = False\n",
    "                if not cuts[i] and col[i] > col[i+1]:\n",
    "                    sign_2 = False\n",
    "                    break\n",
    "            # 如果cuts全都是严格大于,那么就可以返回结果了.\n",
    "            if sign_1:\n",
    "                break\n",
    "            # 如果当前列不满足条件,就需要删除,否则更新cuts\n",
    "            if sign_2:\n",
    "                for i in range(len(col)-1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        ans = 0\n",
    "\n",
    "        # 表示已判断出来字典序关系\n",
    "        increasing = [False] * n\n",
    "\n",
    "        for i in range(m):\n",
    "            flag = True\n",
    "            for j in range(1, n):\n",
    "                if not increasing[j] and strs[j][i] < strs[j-1][i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if not flag:\n",
    "                ans += 1\n",
    "            else:\n",
    "                for j in range(1, n):\n",
    "                    if strs[j][i] > strs[j-1][i] and not increasing[j]:\n",
    "                        increasing[j] = True\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, strs: List[str], index:int, del_lst:List[int]):\n",
    "        n = len(strs[0])\n",
    "        # print(strs,n)\n",
    "        for i in range(1,len(strs)):\n",
    "            left = 0\n",
    "            while left in del_lst or (left<n and strs[i][left]==strs[i-1][left]):\n",
    "                left+=1\n",
    "            # print(left,strs[i][left],strs[i-1][left])\n",
    "            if left<n and strs[i][left]<strs[i-1][left] and left==index:\n",
    "                return False\n",
    "        return True\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        ans = 0\n",
    "        del_lst = []\n",
    "        for i in range(n):\n",
    "            if self.check(strs,i,del_lst):\n",
    "                ans+=0\n",
    "            else:\n",
    "                del_lst.append(i)\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        '''m,n=len(strs),len(strs[0])\n",
    "        flag=[0]*m #flag[i]=1表示strs[i]>strs[i-1]\n",
    "        cnt=0\n",
    "        for i in range(n):#判断是否删除第i个字母\n",
    "            tempflag=[0]*m\n",
    "            isdeleted=False\n",
    "            for j in range(1,m):\n",
    "                if flag[j]:\n",
    "                    tempflag[j]=1\n",
    "                    continue\n",
    "                if strs[j][i]<strs[j-1][i]:\n",
    "                    isdeleted=True\n",
    "                    break\n",
    "                elif strs[j][i]>strs[j-1][i]:\n",
    "                    tempflag[j]=1\n",
    "            if isdeleted:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                flag=tempflag[::]\n",
    "        return cnt'''\n",
    "        '''n,m=len(strs),len(strs[0])\n",
    "        cnt=0\n",
    "        flag=[1]*(n-1)\n",
    "        for i in range(m):\n",
    "            if sum(flag)==0:break\n",
    "            temp=flag[::]\n",
    "            bool_=False\n",
    "            for j in range(n-1):\n",
    "                if temp[j]:\n",
    "                    if strs[j][i]<strs[j+1][i]:\n",
    "                        temp[j]=0\n",
    "                    elif strs[j][i]>strs[j+1][i]:\n",
    "                        bool_=True\n",
    "                        cnt+=1\n",
    "                        break\n",
    "            if not bool_:flag=temp[::]\n",
    "        return cnt'''\n",
    "        n,m=len(strs),len(strs[0])\n",
    "        ret,flag=0,[1]*(n-1)\n",
    "        for i in range(m):\n",
    "            if sum(flag)==0:break\n",
    "            temp=flag[::]\n",
    "            for j in range(n-1):\n",
    "                if flag[j]==0:continue\n",
    "                if strs[j][i]<strs[j+1][i]:\n",
    "                    flag[j]=0\n",
    "                elif strs[j][i]>strs[j+1][i]:\n",
    "                    ret+=1\n",
    "                    flag=temp[::]\n",
    "                    break\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "\n",
    "        def is_sorted(A):\n",
    "            return all(A[i] <= A[i + 1] for i in range(len(A) - 1))\n",
    "\n",
    "        ans = 0\n",
    "        cur = ['' for _ in range(len(strs))]  \n",
    "\n",
    "        for col in zip(*strs):\n",
    "            temp = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                temp[i] = temp[i] + letter\n",
    "\n",
    "            if is_sorted(temp):\n",
    "                cur = temp\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        ans = 0\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        flag = [False] * n\n",
    "\n",
    "        for i in range(m):\n",
    "            sorted_flag = True\n",
    "            for j in range(1, n):\n",
    "                # 前面非递增且j-1 到 递减，无序\n",
    "                if not flag[j] and strs[j][i] < strs[j-1][i]:\n",
    "                    sorted_flag = False\n",
    "                    break\n",
    "            if not sorted_flag:\n",
    "                ans += 1\n",
    "            else:\n",
    "                for j in range(1, n):\n",
    "                    if not flag[j] and strs[j][i] > strs[j-1][i]:\n",
    "                        flag[j] = True\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        cuts = [False] * (len(strs) - 1)\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            if all(cuts[i] or col[i] <= col[i+1] for i in range(len(col)-1)):\n",
    "                for i in range(len(col)-1):\n",
    "                    # col[i] <= col[i+1]不可取是因为当出现 \"xga\",\"xfb\",\"yfa\"时候，需要保证xa, xb有序\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]) -> int:\n",
    "        count=0\n",
    "        record=[False]*(len(A)-1)\n",
    "        for col in zip(*A):\n",
    "            sign1=True\n",
    "            sign2=True\n",
    "            for i in range(len(A)-1):\n",
    "                if record[i]==False:\n",
    "                    sign1=False \n",
    "                    if col[i]>col[i+1]:\n",
    "                        sign2=False \n",
    "                        break\n",
    "            if sign1==True:\n",
    "                break \n",
    "            if sign2==True:\n",
    "                for i in range(len(A)-1):\n",
    "                    if col[i]<col[i+1]:\n",
    "                        record[i]=True\n",
    "                         \n",
    "            else:\n",
    "                count+=1\n",
    "            \n",
    "            \n",
    "        return count\n",
    "\n",
    "#如果大家都和平，直接count结束（sign1)\n",
    "#如果大家有没有不冲突（sign2），如果有冲突直接武力干涉（+1），如果只是可能存在不和平，\n",
    "#看看哪家没有和平（sign2）标false但是武力没有加1\n",
    "#最后知道都和平为止看看用了几次武力"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(strs[0])\n",
    "        num = len(strs)\n",
    "        tmdnk=[ False for i in range(num-1)]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            flag=0\n",
    "            for j in range(num-1):\n",
    "                if (not tmdnk[j]) and strs[j][i]>strs[j+1][i]:\n",
    "                    res+=1\n",
    "                    flag=1\n",
    "                    break\n",
    "            if flag==0:\n",
    "                for j in range(num-1):\n",
    "                    if strs[j][i]<strs[j+1][i]:\n",
    "                        tmdnk[j]=True\n",
    "            # print(tmdnk)\n",
    "        return res \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(strs[0])\n",
    "        num = len(strs)\n",
    "        tmdnk=[ False for i in range(num-1)]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            flag=0\n",
    "            for j in range(num-1):\n",
    "                if (not tmdnk[j]) and strs[j][i]>strs[j+1][i]:\n",
    "                    res+=1\n",
    "                    flag=1\n",
    "                    break\n",
    "            if flag==0:\n",
    "                for j in range(num-1):\n",
    "                    if strs[j][i]<strs[j+1][i]:\n",
    "                        tmdnk[j]=True\n",
    "            # print(tmdnk)\n",
    "        return res \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def is_sorted(arr):\n",
    "            return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))\n",
    "        res = 0\n",
    "        cur = [\"\" for _ in range(len(strs))]\n",
    "        for col in zip(*strs):\n",
    "            curr = cur[:]\n",
    "            for i in range(len(col)):\n",
    "                curr[i] += col[i]\n",
    "            if is_sorted(curr):\n",
    "                cur = curr\n",
    "            else:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                        break\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        ans = 0\n",
    "        gt = [False] * n\n",
    "        gt[0] = True\n",
    "        for col in zip(*strs):\n",
    "            ifdel = False\n",
    "            tmp = gt.copy()\n",
    "            for i in range(1, n):\n",
    "                if gt[i]:\n",
    "                    continue\n",
    "                if col[i] < col[i-1]:\n",
    "                    ifdel = True\n",
    "                    break\n",
    "                elif col[i] > col[i-1]:\n",
    "                    tmp[i] = True\n",
    "            if ifdel:\n",
    "                ans += 1\n",
    "            else:\n",
    "                gt = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        l = len(strs[0])\n",
    "        small = [False] * (n - 1)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            flag = False\n",
    "            for j in range(n - 1):\n",
    "                if small[j]:\n",
    "                    continue\n",
    "                if strs[j][i] > strs[j + 1][i]:\n",
    "                    flag = True\n",
    "                    break\n",
    "            \n",
    "            if flag:\n",
    "                res += 1\n",
    "            else:\n",
    "                for j in range(n - 1):\n",
    "                    if strs[j][i] < strs[j + 1][i]:\n",
    "                        small[j] = True\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        ans = 0\n",
    "        n = len(strs[0])\n",
    "        cur = [\"\"] * len(strs)\n",
    "        for i in range(n):\n",
    "            cur2 = cur[:]\n",
    "            for j in range(len(strs)):\n",
    "                cur2[j] += strs[j][i]\n",
    "            if all(cur2[k] <= cur2[k+1] for k in range(len(cur2) - 1)):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\r\n",
    "        res = 0 \r\n",
    "        # 检测每一组是否有序 \r\n",
    "        # 如果已经有严格降序，就不用都有序\r\n",
    "\r\n",
    "        #g[i][j] 为True表示strs[i] 严格大于 strs[j]\r\n",
    "        g = [[False] * 105 for _ in range(105) ]\r\n",
    "\r\n",
    "        n = len(strs)\r\n",
    "        for j in range(len(strs[0])):\r\n",
    "            chs = []\r\n",
    "            for s in strs:\r\n",
    "                chs.append(s[j])\r\n",
    "            flag = False \r\n",
    "            for i in range(1, len(chs)):\r\n",
    "                for k in range(i):\r\n",
    "                    if g[k][i]:continue\r\n",
    "                    if chs[k] > chs[i]:\r\n",
    "                        # 需要删除\r\n",
    "                        flag = True\r\n",
    "            if flag:\r\n",
    "                # g 关系不需要更新 \r\n",
    "                res += 1\r\n",
    "            else:\r\n",
    "                # 不需要删除，将严格大于的关系更新\r\n",
    "                for i in range(len(chs)):\r\n",
    "                    for k in range(i + 1, len(chs)):\r\n",
    "                        if chs[i] < chs[k]:\r\n",
    "                            g[i][k] = True \r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        cuts = [False for _ in range(len(strs) - 1)]\n",
    "        res = 0\n",
    "        for col in zip(*strs):\n",
    "            if all(cuts[i] or col[i] <= col[i + 1] for i in range(len(col) - 1)):\n",
    "                for i in range(len(col) - 1):\n",
    "                    if col[i] < col[i + 1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        count = 0\n",
    "        last_equal = [True] * (len(strs) - 1)\n",
    "        for j in range(n):\n",
    "            flag, temp = True, [e for e in last_equal]\n",
    "            for i in range(1, len(strs)):\n",
    "                if strs[i][j] < strs[i - 1][j] and temp[i - 1]:\n",
    "                    count += 1\n",
    "                    flag = False\n",
    "                    break\n",
    "                elif strs[i][j] == strs[i - 1][j] and temp[i - 1]:\n",
    "                    flag = False\n",
    "                elif strs[i][j] > strs[i - 1][j]:\n",
    "                    temp[i - 1] = False\n",
    "            else:\n",
    "                last_equal = temp\n",
    "            if flag:\n",
    "                return count\n",
    "       \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n=len(strs)\n",
    "        count=0\n",
    "        flag=-1\n",
    "        while flag!=0:\n",
    "            flag=0\n",
    "            for j in range(len(strs[0])):\n",
    "                if flag:break\n",
    "                pre=strs[0][:j+1]\n",
    "                for i in range(n):\n",
    "                    if flag:break\n",
    "                    if strs[i][:j+1]<pre:\n",
    "                        flag=1\n",
    "                        count+=1\n",
    "\n",
    "                        for k in range(n):\n",
    "                            strs[k]=strs[k][:j]+strs[k][j+1:]\n",
    "                    else:pre=strs[i][:j+1]\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            cnt = 1\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                        break\n",
    "                    cnt += 1\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "                    cnt += 1\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "            if(cnt == m):\n",
    "                return delete_cnt\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m, n = len(strs), len(strs[0])\n",
    "        noCheck = set()\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tag = False\n",
    "            insq = set()\n",
    "            for j in range(m - 1):\n",
    "                if j not in noCheck:\n",
    "                    if strs[j + 1][i] < strs[j][i]:\n",
    "                        tag = True\n",
    "                        break\n",
    "                    elif strs[j + 1][i] > strs[j][i]:\n",
    "                        insq.add(j)\n",
    "            if tag:\n",
    "                ans += 1\n",
    "            else:\n",
    "                noCheck = noCheck | insq\n",
    "                    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]) -> int:\n",
    "        count = 0\n",
    "        # 记录的是满足条件的所有列的每一个元素的的严格大于情况.\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "        \n",
    "        for col in zip(*A):\n",
    "            \n",
    "            # sign_1表示cuts是否全都为True\n",
    "            # sign_2表示当前列是否满足条件\n",
    "            sign_1 = sign_2 = True\n",
    "            for i in range(len(col)-1):\n",
    "                if not cuts[i]:\n",
    "                    sign_1 = False\n",
    "                if not cuts[i] and col[i] > col[i+1]:\n",
    "                    sign_2 = False\n",
    "                    break\n",
    "            # 如果cuts全都是严格大于,那么就可以返回结果了.\n",
    "            if sign_1:\n",
    "                break\n",
    "            # 如果当前列不满足条件,就需要删除,否则更新cuts\n",
    "            if sign_2:\n",
    "                for i in range(len(col)-1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def isSorted(strs):\n",
    "            return all(strs[i] <= strs[i+1] for i in range(len(strs)-1))\n",
    "\n",
    "        ans = 0\n",
    "        # cur : all rows we have written\n",
    "        curr = [''] * len(strs)\n",
    "        # unzip strs\n",
    "        for col in zip(*strs):\n",
    "            curr2 = curr[:]\n",
    "            for i, c in enumerate(col):\n",
    "                curr2[i] = curr2[i] + c\n",
    "\n",
    "            if isSorted(curr2):\n",
    "                curr = curr2\n",
    "            else:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        ans, st = 0, [0 for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            tmp, ok = [0 for _ in range(n)], 1\n",
    "            for j in range(1, n):\n",
    "                l1, l2 = strs[j - 1][i], strs[j][i]\n",
    "                if st[j] == 1 or l1 < l2: tmp[j] = 1\n",
    "                elif l1 > l2:\n",
    "                    ok = 0\n",
    "                    break\n",
    "            if ok == 0: ans += 1\n",
    "            else: st = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        increasing = [False] * n\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            flag = True\n",
    "            for j in range(1, n):\n",
    "                if not increasing[j] and strs[j][i] < strs[j-1][i]:\n",
    "                    ans += 1\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                for j in range(1, n):\n",
    "                    if not increasing[j] and strs[j][i] > strs[j-1][i]:\n",
    "                        increasing[j] = True\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minDeletionSize(self, A):\n",
    "        def is_sorted(A):\n",
    "            return all(A[i] <= A[i+1] for i in range(len(A) - 1))\n",
    "        ans = 0\n",
    "        cur = [\"\"] * len(A)  \n",
    "        for col in zip(*A):\n",
    "            cur2 = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                cur2[i] = cur2[i] + letter\n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 优化贪心\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]):\n",
    "        # cuts[i] is True : we don't need to check col[i] <= col[i+1]\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "\n",
    "        ans = 0\n",
    "        for col in zip(*A):\n",
    "            if all(cuts[i] or col[i] <= col[i+1] for i in range(len(col) - 1)):\n",
    "                for i in range(len(col) - 1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def is_sorted(s):\n",
    "            return all(x <= y for x, y in pairwise(s))\n",
    "        cur = [\"\"] * len(strs)\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            cur2 = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                cur2[i] = cur[i] + letter\n",
    "            \n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minDeletionSize(self, A):\n",
    "        # cuts[i] is True : we don't need to check col[i] <= col[i+1]\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "\n",
    "        ans = 0\n",
    "        for col in zip(*A):\n",
    "            if all(cuts[i] or col[i] <= col[i+1] for i in range(0, len(col) - 1, 1)):\n",
    "                for i in range(0, len(col) - 1, 1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        rows = [(0, m-1)]\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            new_rows = []\n",
    "            deleted = False\n",
    "            for start, end in rows:\n",
    "                new_start = -1\n",
    "                for i in range(start, end):\n",
    "                    if col[i] > col[i+1]:\n",
    "                        deleted = True\n",
    "                        ans += 1\n",
    "                        break\n",
    "                    elif col[i] == col[i+1]:\n",
    "                        if new_start == -1:\n",
    "                            new_start = i\n",
    "                    else:\n",
    "                        if new_start != -1:\n",
    "                            new_rows.append((new_start, i))\n",
    "                            new_start = -1\n",
    "                if new_start != -1:\n",
    "                    new_rows.append((new_start, end))\n",
    "                if deleted:\n",
    "                    break\n",
    "            if deleted:\n",
    "                continue\n",
    "            if not new_rows:\n",
    "                break\n",
    "            rows = new_rows\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        from collections import defaultdict\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        checked = defaultdict(int)\n",
    "        res = 0\n",
    "        for i in range(m): # each index\n",
    "            flag = 1\n",
    "            indices = []\n",
    "            # print(f'i = {i}')\n",
    "            for j in range(n-1): # each word\n",
    "                # print(f'{j}')\n",
    "                if checked[j]:\n",
    "                    # print('skipped')\n",
    "                    continue\n",
    "                if (strs[j][i]) < (strs[j+1][i]):\n",
    "                    indices.append(j)\n",
    "                if strs[j][i] > strs[j+1][i]:\n",
    "                    flag = 0\n",
    "                    res += 1\n",
    "                    # print('false')\n",
    "                    break\n",
    "            if flag:\n",
    "                for j in indices:\n",
    "                    checked[j] = 1\n",
    "                    # print('checked')\n",
    "            # print()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m=len(strs)\n",
    "        n=len(strs[0])\n",
    "        cuts=[False]*(len(strs)-1)\n",
    "        count=0\n",
    "        for col in zip(*strs):\n",
    "           # print(col)\n",
    "            sign1=True\n",
    "            sign2=True\n",
    "            for i in range(len(col)-1):\n",
    "                if not cuts[i]:\n",
    "                    sign1=False\n",
    "                if not cuts[i] and col[i]>col[i+1]:\n",
    "                    sign2=False\n",
    "                    break\n",
    "            if sign1:\n",
    "                break\n",
    "            if sign2:\n",
    "                for i in range(len(col)-1):\n",
    "                    if col[i]<col[i+1]:\n",
    "                        cuts[i]=True\n",
    "            else:\n",
    "                count+=1\n",
    "       # print(cuts)\n",
    "        return count\n",
    "   \n",
    "\n",
    "\n",
    "\n",
    "        #return n-ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        ans = [] \n",
    "        m = len(strs[0])\n",
    "        n = len(strs)\n",
    "        c = [(0, n-1)]\n",
    "        i = 0 \n",
    "        while c and i < m:\n",
    "            #print(c, i)\n",
    "            flag = 1 \n",
    "            for l, r in c:\n",
    "                for j in range(l+1,r+1):\n",
    "                    if ord(strs[j][i]) < ord(strs[j-1][i]):\n",
    "                        flag = 0 \n",
    "                        break \n",
    "            if flag == 0:\n",
    "                ans.append(i) \n",
    "            else:\n",
    "                sz = len(c) \n",
    "                #nl, nr = floag('inf'), 0 \n",
    "                for _ in range(sz):\n",
    "                    l,r = c.pop(0) \n",
    "                    nl, nr = r, l \n",
    "                    for j in range(l+1,r+1):\n",
    "                        if strs[j][i] == strs[j-1][i]:\n",
    "                            nl = min(nl, j-1)\n",
    "                            nr = j \n",
    "                        elif nr > nl:\n",
    "                            c.append((nl, nr))\n",
    "                            nl, nr = r, l \n",
    "                    if nr > nl:\n",
    "                        c.append((nl,nr)) \n",
    "            i+=1 \n",
    "            #print(c, i)\n",
    "         \n",
    "        #print(ans) \n",
    "        return len(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m=len(strs)\n",
    "        n=len(strs[0])\n",
    "        cuts=[False]*(len(strs)-1)\n",
    "        count=0\n",
    "        for col in zip(*strs):\n",
    "            sign1=True\n",
    "            sign2=True\n",
    "\n",
    "            for i in range(m-1):\n",
    "                if not cuts[i]:\n",
    "                    sign1=False\n",
    "                if not cuts[i] and col[i]>col[i+1]:\n",
    "                    sign2=False\n",
    "                    break\n",
    "            if sign1:\n",
    "                break \n",
    "            if sign2:\n",
    "                for i in range(m-1):\n",
    "                    if col[i]<col[i+1]:\n",
    "                        cuts[i]=True\n",
    "            else:\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "\n",
    "        vis = [False] * (m-1)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(m-1):\n",
    "                if not vis[j] and strs[j][i] > strs[j+1][i]:\n",
    "                    res += 1\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                for j in range(m-1):\n",
    "                    if strs[j][i] < strs[j+1][i]:\n",
    "                        vis[j] = True\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                        break\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def is_sorted(x):\n",
    "            return all(x[i] <= x[i+1] for i in range(len(x)-1))\n",
    "        cur = ['']*len(strs)\n",
    "        # *strs将每一列的元素放一起\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            cur2 = cur[:]\n",
    "            for j,c in enumerate(col):\n",
    "                cur2[j] = cur2[j]+c\n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        m = len(strs)\n",
    "        lst = ['' for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            flag = 2\n",
    "            lstNew = []\n",
    "            num = 0\n",
    "            for j in range(m):\n",
    "                s = strs[j]\n",
    "                lstNew.append(lst[j] + s[i])\n",
    "                numNow = ord(s[i])\n",
    "                if numNow > num:\n",
    "                    num = ord(s[i])\n",
    "                elif numNow == num and flag != 0:\n",
    "                    flag = 1\n",
    "                else:\n",
    "                    flag = 0\n",
    "            if flag == 0:\n",
    "                if sorted(lstNew) == lstNew:\n",
    "                    lst = lstNew\n",
    "            else:\n",
    "                lst = lstNew\n",
    "        return n - len(lst[0])\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[int]):\n",
    "        def is_sorted(A):\n",
    "            return all(A[i] <= A[i+1] for i in range(len(A) - 1))\n",
    "\n",
    "        ans = 0\n",
    "        # cur : all rows we have written\n",
    "        # For example, with A = [\"abc\",\"def\",\"ghi\"] we might have\n",
    "        # cur = [\"ab\", \"de\", \"gh\"].\n",
    "        cur = [\"\"] * len(A)  \n",
    "\n",
    "        for col in zip(*A):\n",
    "            # cur2 : What we potentially can write, including the\n",
    "            #        newest column 'col'.\n",
    "            # Eg. if cur = [\"ab\",\"de\",\"gh\"] and col = (\"c\",\"f\",\"i\"),\n",
    "            # then cur2 = [\"abc\",\"def\",\"ghi\"].\n",
    "            cur2 = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                cur2[i] = cur2[i] + letter\n",
    "\n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        d = [0]\n",
    "        n = len(strs)\n",
    "        for i in range(n):\n",
    "            strs[i] += 'z'\n",
    "        n,m = len(strs), len(strs[0])\n",
    "        for i in range(1,m):\n",
    "            d.append(i)\n",
    "            for j in range(i):\n",
    "                f = 1\n",
    "                for t in range(n):\n",
    "                    if strs[t][j] > strs[t][i]:\n",
    "                        f = 0\n",
    "                        break\n",
    "                if f:\n",
    "                    d[i] = min(d[i], d[j] + (i-j-1))\n",
    "        return d[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        \"\"\"\n",
    "        dp[i]代表每个str[k:]时所保存的最大列数\n",
    "        m =len(strs[0]) #是字符的长度\n",
    "        转移方程就是dp[i] = max(dp[j]+1) for j in range(i+1,w)遍历子串得到最大值，且需要满足条件str[i]<=str[j] for str in strs保证是递增\n",
    "        最后删除最大的保存列 得到的就是需要删除的最小的列 \n",
    "        \"\"\"\n",
    "        n,m = len(strs),len(strs[0])\n",
    "        dp = [1 for _ in range(m)]\n",
    "        for i in range(m-2,-1,-1):#从倒数第二位开始处理\n",
    "            for j in range(i+1,m):\n",
    "                if all(word[i]<=word[j] for word in strs):#需要满足所有单词都递增的条件\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\n",
    "        return m-max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "\n",
    "\n",
    "        n,m=len(strs),len(strs[0])\n",
    "        dp=[1]*m\n",
    "        for i in range(m):\n",
    "            for j in range(i):\n",
    "                for k in range(n):\n",
    "                    if strs[k][i]<strs[k][j]:\n",
    "                        break\n",
    "                else:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "\n",
    "        return m-max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        W = len(strs[0])\n",
    "        dp = [1] * W\n",
    "        for i in range(W-2, -1, -1):\n",
    "            for j in range(i+1, W):\n",
    "                if all(row[i] <= row[j] for row in strs):\n",
    "                    dp[i] = max(dp[i], 1 + dp[j])\n",
    "\n",
    "        return W - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        dp = [1]*m\n",
    "        for i in range(1,m):\n",
    "            for j in range(i):\n",
    "                if all(strs[k][j] <= strs[k][i] for k in range(n)):\n",
    "                    dp[i] = max(dp[i], dp[j]+1)\n",
    "        return m - max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        dp = [1] * m\n",
    "        ans = 1\n",
    "        for i in range(m):\n",
    "            for j in range(0, i):\n",
    "                ok = True\n",
    "                for k in range(n):\n",
    "                    if strs[k][j] > strs[k][i]:\n",
    "                        ok = False\n",
    "                if ok:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "                ans = max(ans, dp[i])\n",
    "        return m - ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        dp = []\n",
    "        \"\"\"\n",
    "        dp[i] x[i] keep num \n",
    "        \"\"\"\n",
    "        s_len = len(strs[0])\n",
    "        dp = [1] * s_len\n",
    "        for i in range(0, s_len):\n",
    "            for j in range(i+1, s_len):\n",
    "                r = True\n",
    "                for line in strs:\n",
    "                    if line[j] < line[i]:\n",
    "                        r = False\n",
    "                if r:\n",
    "                    dp[j] = max(dp[j], dp[i]+ 1)\n",
    "        return s_len - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        rows, cols = len(strs), len(strs[0])\n",
    "        # dp[c]: max cols to keep until index i\n",
    "        dp = [1] * cols\n",
    "        ans = 0\n",
    "        for c2 in range(cols):\n",
    "            for c1 in range(c2):\n",
    "                if all(strs[r][c2] >= strs[r][c1] for r in range(rows)):\n",
    "                    dp[c2] = max(dp[c2], dp[c1] + 1)\n",
    "            ans = max(ans, dp[c2])\n",
    "        return cols - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judge(self, strs, i, j):\n",
    "        for k in range(len(strs)):\n",
    "            if ord(strs[k][i]) < ord(strs[k][j]):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        dp = [1] * len(strs[0]) #最长升序\n",
    "        for i in range(1, len(strs[0])):\n",
    "            for j in range(i):\n",
    "                if self.judge(strs, i, j):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        \n",
    "        return len(strs[0]) - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        keep=1\n",
    "        \n",
    "        m,n=len(strs),len(strs[0])\n",
    "        dp=[1]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if all(strs[m][j]>=strs[m][i] for m in range(m)):\n",
    "                    dp[j]=max(dp[j],dp[i]+1)\n",
    "        keep=max(dp)\n",
    "        return n-keep\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        W = len(strs[0])\n",
    "        dp = [1] * W\n",
    "        for i in range(W-1, -1, -1):\n",
    "            for j in range(i+1, W):\n",
    "                if all(row[i] <= row[j] for row in strs):\n",
    "                    dp[i] = max(dp[i], 1+dp[j])\n",
    "        return W - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, i):\n",
    "                if all(row[j] <= row[i] for row in strs):\n",
    "                    dp[i] = max(dp[i], 1 + dp[j])\n",
    "        return n - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n=len(strs)\n",
    "        l=len(strs[0])\n",
    "        \n",
    "        def check(j,i):\n",
    "            for s in strs:\n",
    "                if s[j]>s[i]:\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "        dp=[1]*l\n",
    "        ans=l\n",
    "        if l==1:\n",
    "            return 0\n",
    "        for i in range(1,l):\n",
    "            for j in range(i):\n",
    "                if check(j,i):\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "\n",
    "            ans=min(ans,l-dp[i])\n",
    "        print(dp)\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        strL = len(strs[0])\n",
    "        dp = [1] * strL\n",
    "        for i in range(1, strL):\n",
    "            for j in range(i):\n",
    "                if all(r[i] >= r[j] for r in strs) and dp[i] < dp[j] + 1:\n",
    "                    dp[i] = dp[j] + 1\n",
    "        return strL - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        # N维最长上升子序列\n",
    "        m,n = len(strs),len(strs[0])\n",
    "        f = [1]*n\n",
    "\n",
    "        for j in range(n):\n",
    "            for k in range(j + 1,n):\n",
    "                if all(row[k] >= row[j] for row in strs):\n",
    "                    f[k] = max(f[k],f[j] + 1)\n",
    "        return n - max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        strlen = len(strs[0])\n",
    "        rs = []\n",
    "        maxlen = 1\n",
    "        for i in range(strlen):\n",
    "            rs.append(1)\n",
    "            for j in range(i):\n",
    "                flag = True\n",
    "                for k in range(len(strs)):\n",
    "                    if strs[k][i]<strs[k][j]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    rs[i] = max(rs[i], rs[j]+1)\n",
    "            maxlen = max(maxlen,rs[i])\n",
    "        return strlen-maxlen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        def less(s1, s2):\n",
    "            for i in range(n):\n",
    "                if s1[i] > s2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        d = []\n",
    "        for i in range(m):\n",
    "            t = ''\n",
    "            for j in range(n):\n",
    "                t = t + strs[j][i]\n",
    "            d.append(t)\n",
    "        dp = [0] * (m + 1)\n",
    "        for i in range(1, m+1):\n",
    "            dp[i] = 1\n",
    "            for j in range(1, i):\n",
    "                if less(d[j-1], d[i-1]):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return (m - max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n=len(strs[0])\n",
    "        k=len(strs)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                find=False\n",
    "                for l in range(k):\n",
    "                    if strs[l][i]<strs[l][j]:\n",
    "                        find=True\n",
    "                        break\n",
    "                if not find:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "        return n-max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n=len(strs)\n",
    "        l=len(strs[0])\n",
    "        ans=l\n",
    "        def check(j,i):\n",
    "            for s in strs:\n",
    "                if s[j]>s[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        dp=[1]*l\n",
    "        if l==1:\n",
    "            return 0\n",
    "\n",
    "        for i in range(1,l):\n",
    "            for j in range(i):\n",
    "                if check(j,i):\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "            \n",
    "            ans=min(ans,l-dp[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m, n = len(strs), len(strs[0])\n",
    "        res = [0]\n",
    "        for i in range(1, n):\n",
    "            tmp = i\n",
    "            for j in range(i):\n",
    "                ok = 1\n",
    "                for k in range(m):\n",
    "                    if strs[k][j] > strs[k][i]:\n",
    "                        ok = 0\n",
    "                        break\n",
    "                if ok == 1: tmp = min(tmp, res[j] + i - j - 1)\n",
    "            res.append(tmp)\n",
    "        return min([res[i] + n - i - 1 for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        dp = [1] * n\n",
    "        ans = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if all(w[i] >= w[j] for w in strs):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return n - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "\n",
    "\n",
    "        n,m=len(strs),len(strs[0])\n",
    "        dp=[1]*m\n",
    "        for i in range(m):\n",
    "            for j in range(i):\n",
    "                if all(strs[k][i]>=strs[k][j] for k in range(n)):\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "                # for k in range(n):\n",
    "                #     if strs[k][i]<strs[k][j]:\n",
    "                #         break\n",
    "                # else:\n",
    "                #     dp[i]=max(dp[i-1],dp[j]+1)\n",
    "                #     print(i,dp[i])\n",
    "        print(dp)\n",
    "        return m-max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m, n = len(strs), len(strs[0])\n",
    "        dp = [1] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if all(strs[k][j] <= strs[k][i] for k in range(m)):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "                    \n",
    "        return n - max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "\n",
    "\n",
    "        \n",
    "        n,m = len(strs),len(strs[0])\n",
    "        dp =[1]*m\n",
    "        for i in range(1,m):\n",
    "            for j in range(i):\n",
    "                if all([ strs[k][j]<=strs[k][i]   for k in range(n)]):\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\n",
    "        \n",
    "        return m-max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        dp = [1] * n\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                if all(w[i] <= w[j] for w in strs):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "\n",
    "        return n - max(dp) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "\n",
    "        dp = [0]*n\n",
    "        for i in range(1,n):\n",
    "            dp[i] = min(i, i, *[dp[j]+i-j-1 for j in range(i) if all([s[j]<=s[i] for s in strs])])\n",
    "\n",
    "        return min(n, *[dp[i]+n-i-1 for i in range(n)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        pre_dict = {}\n",
    "        nxt_dict = defaultdict(list)\n",
    "        n = len(strs[0])\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                flag = True\n",
    "                for s in strs:\n",
    "                    if s[i] > s[j]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    pre_dict[j] = i\n",
    "                    nxt_dict[i].append(j)\n",
    "        max_length = [0]\n",
    "        max_length_dict = {}\n",
    "\n",
    "        def dfs(cur, cur_length):\n",
    "            if cur in max_length_dict and cur_length <= max_length_dict[cur]:\n",
    "                return\n",
    "            max_length_dict[cur] = cur_length\n",
    "            if len(nxt_dict[cur]) == 0:\n",
    "                max_length[0] = max(max_length[0], cur_length)\n",
    "                return\n",
    "            for nxt in nxt_dict[cur]:\n",
    "                dfs(nxt, cur_length + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in pre_dict:\n",
    "                dfs(i, 1)\n",
    "        return n - max_length[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        @cache \n",
    "        def dp(i):\n",
    "            if i == 0: return 1\n",
    "\n",
    "            res = 1\n",
    "            for j in range(i):\n",
    "                if all([strs[t][i] >= strs[t][j] for t in range(n)]):\n",
    "                    res = max(res, dp(j) + 1)\n",
    "            return res \n",
    "        \n",
    "        return m - max(dp(i) for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        # pre是上一列的答案\n",
    "        @cache\n",
    "        def dfs(index, pre):\n",
    "            if index == m:\n",
    "                return 0\n",
    "            res = 1 + dfs(index + 1, pre)\n",
    "            if pre == -1 or all(s[pre] <= s[index] for s in strs):\n",
    "                res = min(res, dfs(index + 1, index))\n",
    "            return res\n",
    "        ans = dfs(0, -1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        \n",
    "        m , n = len(strs) , len(strs[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i == n:return 0\n",
    "            ans = dfs(i+1,j) + 1\n",
    "            if j == -1 or all([s[i] >= s[j] for s in strs]):\n",
    "                ans = min(ans,dfs(i+1,i))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        #copy 记忆化搜索\n",
    "        l = len(strs[0])\n",
    "        @cache\n",
    "        def dfs(idx,preidx):\n",
    "            if idx == l:\n",
    "                return 0\n",
    "            ans = dfs(idx+1,preidx)\n",
    "            if preidx == -1 or all(s[idx]>= s[preidx] for s in strs):\n",
    "                ans = max(ans,1+dfs(idx+1,idx))\n",
    "            return ans\n",
    "        return l - dfs(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "\n",
    "        @cache \n",
    "        def calc(i, j):\n",
    "            return all([strs[t][i] >= strs[t][j] for t in range(n)])\n",
    "\n",
    "        @cache \n",
    "        def dp(i):\n",
    "            if i == 0: return 1\n",
    "\n",
    "            res = 1\n",
    "            for j in range(i):\n",
    "                if calc(i, j):\n",
    "                    res = max(res, dp(j) + 1)\n",
    "            return res \n",
    "        \n",
    "        return m - max(dp(i) for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        \"\"\"\n",
    "        :param strs:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(strs[0])\n",
    "        @lru_cache(None)\n",
    "        def get_min_del(idx, last_idx = -1):\n",
    "            if idx == len1:\n",
    "                return 0\n",
    "            if last_idx == -1:\n",
    "                return min(get_min_del(idx+1, last_idx) + 1, get_min_del(idx+1, idx))\n",
    "            else:\n",
    "                for i in range(len(strs)):\n",
    "                    if strs[i][idx] < strs[i][last_idx]:\n",
    "                        return get_min_del(idx+1, last_idx) + 1\n",
    "                return min(get_min_del(idx+1, last_idx) + 1, get_min_del(idx+1, idx))\n",
    "        return get_min_del(0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
